package com.yanceysong.codetop.s61_s70;

import java.util.LinkedList;
import java.util.Stack;

public class S64_Mid_394_字符串解码 {
    // 指针用于递归实现中全局记录当前解析到的字符串位置
    int ptr;

    /**
     * .S64_Mid_394_字符串解码
     * .<p>
     * .题目链接：<a href="https://leetcode.cn/problems/decode-string/">https://leetcode.cn/problems/decode-string/</a>
     * .<p>
     * .题目描述：
     * .给定一个经过编码的字符串 s，返回它解码后的字符串。编码规则形如：k[encoded_string]，表示方括号里的 encoded_string 重复 k 次。
     * .其中 k 是正整数，且输入保证格式合法：
     * .- 不会出现非法括号匹配或乱序；
     * .- 数字只表示重复次数（原始数据部分不含数字）；
     * .- 不存在诸如 3a、2[4] 等无效形式。
     * .支持嵌套：例如 3[a2[c]] => a2[c] 展开为 acc；再整体重复3次 => accaccacc。
     * .<p>
     * .示例：
     * .1) s = "3[a]2[bc]"      -> "aaabcbc"
     * .2) s = "3[a2[c]]"       -> "accaccacc"
     * .3) s = "2[abc]3[cd]ef" -> "abcabccdcdcdef"
     * .4) s = "abc3[cd]xyz"   -> "abccdcdcdxyz"
     * .5) s = "10[a]"         -> "aaaaaaaaaa"
     * .6) s = "2[3[a]b]"      -> "aaabaaab"
     * .7) s = ""              -> "" (空串)
     * .8) s = "plain"         -> "plain" (无编码)
     * .<p>
     * .核心标签：栈 / 递归 / 字符串 / 模拟 / 深度优先解析 / 状态机
     * .<p>
     * .解题思路（两种主流实现）：
     * .1. 栈模拟法（迭代）：
     * .   - 单次线性扫描，把字符逐个压栈；遇到 ']' 时开始回溯：
     * .     提取最近的一个“[”之间的编码片段 encoded_string；再向左弹出所有连续数字形成重复次数 k；
     * .     然后将 decoded(encoded_string, k) 重新逐字符压回栈顶（相当于局部展开）。
     * .   - 最终栈中字符顺序即完整结果。
     * .2. 递归解析法（DFS）：
     * .   - 使用全局指针 ptr，从左到右：
     * .     如果遇到字母，直接加入当前构建结果；
     * .     如果遇到数字，解析完整数字 k 后跳过 '[' ，递归解析内部子串 inner（直到遇到与之匹配的 ']'）；
     * .     返回时把 inner 重复 k 次并附加到结果。遇到 ']' 就结束当前层。
     * .<p>
     * .ASCII 栈回溯示意（示例 "3[a2[c]]"）：
     * .输入: 3 [ a 2 [ c ] ]
     * .扫描过程（栈顶在右侧）：
     * .push 3 -> [3]
     * .push [ -> [3,[]
     * .push a -> [3,[,a]
     * .push 2 -> [3,[,a,2]
     * .push [ -> [3,[,a,2,[ ]
     * .push c -> [3,[,a,2,[,c]
     * .遇到 ']' -> 弹出直到 '[' 得到 "c"；读取左侧数字 2；展开为 "cc" 压回 => [3,[,a,c,c]
     * .遇到 ']' -> 弹出直到 '[' 得到 "acc"；读取左侧数字 3；展开为 "accaccacc" 压回 => [a,c,c,a,c,c,a,c,c]
     * .最终结果：accaccacc
     * .<p>
     * .关键洞察：
     * .- 读取数字时要处理多位数（如 12[a]）。栈法通过反向位权累乘处理；递归法直接累积构造整数。
     * .- 嵌套结构天然适合栈或递归；不必显式构造语法树。
     * .- 出栈时的顺序是反的，因此用 StringBuilder.insert(0, ch) 或先反转再使用；本实现采用前插确保正确顺序。
     * .- 当没有数字包裹时（纯字母），直接原样返回即可，不影响逻辑。
     * .- 输出长度可能远大于输入，需要在复杂度分析中以“输出总长度 M”衡量。
     * .<p>
     * .复杂度分析：
     * .- 设输入长度为 N，输出解码后长度为 M。
     * .- 时间：O(N + M)。每个输入字符处理一次；每个输出字符产生一次。
     * .- 空间：O(N + M)。栈/递归调用深度最坏为嵌套层数（<= N），结果字符串占 M。
     * .<p>
     * .常见陷阱：
     * .- 多位数字解析错误（忽略进位或顺序）。
     * .- 忘记在递归中移动指针或跳过 '[' 与 ']'。
     * .- 使用 String 重复拼接导致性能退化（应用 StringBuilder + 自定义 repeat）。
     * .- 忘记处理无括号的纯字符串情况。
     * .<p>
     * .可扩展点：
     * .- 若允许字母与数字混合原始内容（题目不需要），需更复杂的判定逻辑。
     * .- 可将解码过程抽象为通用“括号倍数展开”语法解析，为后续支持如花括号或其他分隔符做准备。
     */
    public String decodeString(String s) {
        // 栈法实现（迭代）
        Stack<Character> charStack = new Stack<>();
        for (int idx = 0; idx < s.length(); idx++) {
            char currentChar = s.charAt(idx);
            if (currentChar != ']') { // 非右括号：直接压栈
                charStack.push(currentChar);
                continue;
            }
            // Step1: 弹出直到 '[' 的编码片段（逆序组装再反转或前插）
            StringBuilder encodedSegmentBuilder = new StringBuilder();
            while (!charStack.isEmpty() && charStack.peek() != '[') {
                encodedSegmentBuilder.insert(0, charStack.pop()); // 前插恢复顺序
            }
            // 弹出 '['
            if (!charStack.isEmpty() && charStack.peek() == '[') {
                charStack.pop();
            }
            // Step2: 解析重复次数（可能是多位数），数字在栈中被顺序压入，其弹出顺序为从末位到首位。
            int repeatCount = 0;
            int placeValue = 1; // 位权（1,10,100...）
            while (!charStack.isEmpty()) {
                char top = charStack.peek();
                if (top < '0' || top > '9') break;
                charStack.pop();
                repeatCount += (top - '0') * placeValue; // 反向累加
                placeValue *= 10;
            }
            if (repeatCount == 0) { // 安全兜底（题目保证合法，一般不会出现）
                repeatCount = 1;
            }
            // Step3: 将展开结果重新压栈
            String segment = encodedSegmentBuilder.toString();
            for (int r = 0; r < repeatCount; r++) {
                for (int c = 0; c < segment.length(); c++) {
                    charStack.push(segment.charAt(c));
                }
            }
        }
        // 全部处理完毕：栈中依旧是正序（底到顶），需要弹出拼接成最终字符串
        StringBuilder resultBuilder = new StringBuilder();
        while (!charStack.isEmpty()) {
            resultBuilder.insert(0, charStack.pop());
        }
        return resultBuilder.toString();
    }

    // ================= 递归实现（对照学习用） =================
    public String decodeStringRecursive(String s) {
        ptr = 0; // 重置指针
        return parseRecursive(s);
    }

    // 解析直到遇到 ']' 或结束；返回当前层展开后的字符串
    private String parseRecursive(String s) {
        StringBuilder layerBuilder = new StringBuilder();
        while (ptr < s.length() && s.charAt(ptr) != ']') {
            char ch = s.charAt(ptr);
            if (Character.isDigit(ch)) {
                // 读取完整数字
                int num = 0;
                while (ptr < s.length() && Character.isDigit(s.charAt(ptr))) {
                    num = num * 10 + (s.charAt(ptr) - '0');
                    ptr++;
                }
                // 跳过 '['
                if (ptr < s.length() && s.charAt(ptr) == '[') {
                    ptr++; // 跳过左括号
                }
                // 递归解析内部内容
                String inner = parseRecursive(s);
                // 跳过与之匹配的 ']'
                if (ptr < s.length() && s.charAt(ptr) == ']') {
                    ptr++;
                }
                // 将 inner 重复 num 次
                layerBuilder.append(repeatString(inner, num));
            } else {
                // 普通字母直接加入
                layerBuilder.append(ch);
                ptr++;
            }
        }
        return layerBuilder.toString();
    }

    // 手写 repeat，兼容较低 Java 版本
    private String repeatString(String str, int count) {
        if (count <= 0) return "";
        return str.repeat(count);
    }

    // 原辅助方法（保持但当前实现未直接使用）
    public String getDigits(String s) {
        StringBuilder ret = new StringBuilder();
        while (ptr < s.length() && Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }

    public String getString(LinkedList<String> v) {
        StringBuilder ret = new StringBuilder();
        for (String str : v) {
            ret.append(str);
        }
        return ret.toString();
    }

    // ===================== 测试代码区域 =====================
    public static void main(String[] args) {
        S64_Mid_394_字符串解码 solver = new S64_Mid_394_字符串解码();
        System.out.println("=== 字符串解码 测试开始 ===\n");

        // 基础示例测试
        testCase(solver, "3[a]2[bc]", "aaabcbc", "示例1 基础+两个片段");
        testCase(solver, "3[a2[c]]", "accaccacc", "示例2 嵌套");
        testCase(solver, "2[abc]3[cd]ef", "abcabccdcdcdef", "示例3 多段+尾随");
        testCase(solver, "abc3[cd]xyz", "abccdcdcdxyz", "示例4 前后字母");

        // 多位数字
        testCase(solver, "10[a]", "aaaaaaaaaa", "多位数字 10[a]");
        testCase(solver, "12[b]", repeatExpect("b", 12), "多位数字 12[b]");

        // 深度嵌套
        testCase(solver, "2[3[a]b]", "aaabaaab", "深度嵌套 2[3[a]b]");
        testCase(solver, "3[z2[y]x]", "zyyxzyyxzyyx", "深度嵌套 混合");

        // 相邻结构 & 无括号纯文本
        testCase(solver, "plain", "plain", "无编码纯文本");
        testCase(solver, "2[a]2[b]2[c]", "aabbcc", "多个相邻结构");

        // 包含不同长度片段
        testCase(solver, "2[ab3[c]]", "abcccabccc", "片段内部再重复");

        // 空串
        testCase(solver, "", "", "空字符串");

        // 递归实现一致性随机测试
        randomConsistencyTest(solver);

        // 较大重复测试（性能）
        largeRepeatTest(solver);

        System.out.println("\n=== 所有测试完成 ===");
    }

    private static void testCase(S64_Mid_394_字符串解码 solver, String input, String expected, String desc) {
        String iterative = solver.decodeString(input);
        String recursive = solver.decodeStringRecursive(input);
        boolean pass = iterative.equals(expected) && recursive.equals(expected);
        System.out.printf("%-20s | 输入=%s | 迭代=%s | 递归=%s | 期望=%s | %s\n",
                desc, input, iterative, recursive, expected, pass ? "✓" : "✗");
        assert pass : desc + " 测试失败";
    }

    private static String repeatExpect(String s, int times) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < times; i++) sb.append(s);
        return sb.toString();
    }

    // 随机构造若干小规模字符串进行两种实现一致性校验
    private static void randomConsistencyTest(S64_Mid_394_字符串解码 solver) {
        System.out.println("\n--- 随机一致性测试 ---");
        java.util.Random rand = new java.util.Random(42);
        String baseChars = "abc"; // 限制字符集（原题不包含数字作为原始字符）
        for (int t = 0; t < 20; t++) {
            String generated = generateRandomEncoded(rand, baseChars, 0, 3);
            String a = solver.decodeString(generated);
            String b = solver.decodeStringRecursive(generated);
            if (!a.equals(b)) {
                System.out.println("不一致: " + generated + " -> iter=" + a + ", rec=" + b);
                assert false : "随机一致性失败";
            }
        }
        System.out.println("随机 20 例 两实现结果一致 ✓");
    }

    // 递归生成随机编码字符串（控制嵌套深度）
    private static String generateRandomEncoded(java.util.Random rand, String chars, int depth, int maxDepth) {
        if (depth >= maxDepth || rand.nextDouble() < 0.3) {
            // 返回一个纯字母片段 (1~3长度)
            int len = 1 + rand.nextInt(3);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < len; i++) sb.append(chars.charAt(rand.nextInt(chars.length())));
            return sb.toString();
        }
        int repeat = 1 + rand.nextInt(5); // 1~5 次重复
        return repeat + "[" + generateRandomEncoded(rand, chars, depth + 1, maxDepth) + "]" + (rand.nextDouble() < 0.5 ? generateRandomEncoded(rand, chars, depth + 1, maxDepth) : "");
    }

    // 大重复测试：验证性能 & 正确性
    private static void largeRepeatTest(S64_Mid_394_字符串解码 solver) {
        System.out.println("\n--- 大重复性能测试 ---");
        String input = "50[ab]"; // 100字符输出
        String expected = repeatExpect("ab", 50);
        String out = solver.decodeString(input);
        assert out.equals(expected) : "大重复迭代失败";
        String out2 = solver.decodeStringRecursive(input);
        assert out2.equals(expected) : "大重复递归失败";
        System.out.println("50[ab] 输出长度=" + out.length() + " ✓");
    }
}
